/*
剑指 Offer II 014. 字符串中的变位词
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

 

示例 1：

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False
 

提示：

1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
 

注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/
*/

/*
wrong answer
//even if use prime to caculate the sum,but still can sum be equal string not equal,
such as kki and qff has the same sum but not equal
even the xor sum is not help
the failing 2rd testcase from last

"snvrcpaywg"
"bpzqiabvfoycdesgjqzijqwdgvsetpbxltggvngvitbddfoatgxjgweahffmlfbnrqjxntqoxshzrvwsvchxhlwjablxfxebdlyyogepeoevrozsmuhxtzwuanrzjqsjpfcnoxzmkfskvttwbbijgnvmlvrhusyncngiagjveozhyeyaqgqqwawbckimryslymostqrgbfaqfnzyczijisjwtuvlufvaugeebmkwxrouvzhfujlhwbwhfgkanjkbvoqmtyabcbwrkpuognuyhjzvxktsouwrfpsqrpcrrzqyuvxawkijnoznlxouhuwgwkfuihnjtcklvpgrzzblybnoznhsqyvyjoyzxkdbznhidzuwqbsjjtcsixxfjhvdvsmhtgepexrhddybqncmsomhxjgiruedpsrsasnosxavmomyxhdkeziwapjkscapaerzxstvfygmqdejitsefuiubyzclqtsxjhadtsybhmyrbjtqaxjkmhzwmqndlxuxvsuudnxqpaveddpkqbeziiziywtzazgpinmnzspruzvhelzseioyrdjsqjshmczkvrkqylbmxsrbaxcvisqkfcosonnfbveucnkcinfazivtfbcarkmpkyggiondhpzrcwefsozefgpftoikjwqgyxbyxucjsrmhecuyybqkyipbpxuncpobfmwjlwjluricyzjvrlqtqpdhqfyoezqshascjpqamewpharnsmlfzoorxtpuwpnbkgpzkganupisydhbzfrzhzvanspwrnvcaypomxiwzenytaodqmgeayivdwiifgkpaicihqhgmvjmromkclqrfgpkeoirinccsxvmylxcgqdktusjpxwmqxasmwloxjyjxqqkghqipztfuygkqpkywtywdoxdeljwttcwanolzdacvsnxqbdmbswhzzfzxogpcsxxasgzzqqekabfpnjkkltdrufgukbporvabcbhslxvpdiogmrrtvncqmpykeqaklzwylbvbxlrnwrxosmgdbpilqhbdlbduygiukhflnwoshsmuauiqrwvrpiqekhpziipcphktcwppsvxtrpxiyubxymkzvdnvqazvuhjpayuorhfeknrkwjjzwwycorfjilaabtfgyqpqzxlfrlufdzxujanmyhmalqlkbhnydmbftgcxqitabxhiehmuwauinaukktcubfdhchzmouqfvhzijfitfjbnlnwkupdvqniylsufidhmmszwcipxkktmnruthlxtdnekdjcoxhhyiesazkwqgfusfaevniordhhazhslskhzepyzkpwstea"
*/

/*
the last failing output

m = 760,s1value:s,s2value=z
m = 761,s1value:n,s2value=k
m = 762,s1value:v,s2value=g
m = 763,s1value:r,s2value=a
m = 764,s1value:c,s2value=n
m = 765,s1value:p,s2value=u
m = 766,s1value:a,s2value=p
m = 767,s1value:y,s2value=i
m = 768,s1value:w,s2value=s
m = 769,s1value:g,s2value=y
*/

#include <unordered_map>
#include <string>
#include <vector>

using namespace std;
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int sum0 = 0;
        int s1_len = s1.size();
        vector<int> primeNum = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
        for(int i = 0; i < s1_len;++i)
        {
            //convert a-z to 26 primer num,avoid ambiguous
            int index = s1[i] - 'a';
            sum0 += primeNum[index];
        }

        int sum1 = 0;
        unordered_map<int,int> alphaSumMap;
        //add sum == 0's index to -1
        //for first character length caculate 
        alphaSumMap[0] = -1;
        for(int j = 0;j <s2.size();++j )
        {
            //convert a-z to 26 primer num,avoid ambiguous
            int index = s2[j] - 'a';
            sum1 += primeNum[index];
            if(alphaSumMap.find(sum1-sum0) != alphaSumMap.end() && (j - alphaSumMap[sum1-sum0] == s1_len))
            {
                int startIndex = alphaSumMap[sum1-sum0] + 1;
                // printf("j=%d,sum1=%d,sum0=%d,alphaNum=%d\n",j,sum1,sum0,startIndex);
                int xorResult = 0;
                for(int m = startIndex; m <= j; ++m)
                {
                    int s1Index = s1[m-startIndex] - 'a';
                    int s1Value = primeNum[s1Index];
                    int s2Index = s2[m] - 'a';
                    int s2Value = primeNum[s2Index];
                    printf("m = %d,s1value:%c,s2value=%c\n",m,s1[m-startIndex],s2[m]);
                    xorResult ^= (s1Value ^ s2Value);
                    
                }
                if(xorResult == 0)
                {
                    return true;
                }
            }
            
            alphaSumMap[sum1] = j;
        }

        return false;
    }
};

//slide window solution
//s1_len:the length of 
//every s1_len in s2,if check if equal to s1
// 
class Solution2 {
public:
    bool checkInclusion(string s1, string s2) {
        int s1_len = s1.size();
        int s2_len = s2.size();
        if(s1_len > s2_len)
        {
            return false;
        }

        vector<int> cnt(26);
        for(int i = 0;i < s1_len;++i)
        {
            --cnt[s1[i] - 'a'];
            ++cnt[s2[i] - 'a'];
        }

        int diff = 0;
        for(int num : cnt)
        {
            if(num != 0)
            {
                ++diff;
            }
        }

        if(diff == 0)
        {
            return true;
        }

        //slide window
        //the substring 
        //保证区间长度为 n(s1_len) 的情况下，去考察是否存在一个区间使得 cnt 的值全为 0。
        for(int j = s1_len;j < s2_len; ++j)
        {
            //head index,to be leave the window
            char c1 = s2[j-s1_len] - 'a';
            //tail index,current character
            char c2 = s2[j] - 'a';

            //c1 is in the left of slide window
            //now leave the left by step 1
            if(cnt[c1] == 0)
            {
                ++diff;
            }

            //leave the slide range,so subtract
            --cnt[c1];
            //after leave,check wether c1 is balance
            if(cnt[c1] == 0)
            {
                --diff;
            }

            //if c2 is balance before
            //now is not balance
            if(cnt[c2] == 0)
            {
                ++diff;
            }

            ++cnt[c2];
            //if c2 is not balance before
            //check after plus 1 if balance now
            if(cnt[c2] == 0)
            {
                --diff;
            }

            if(diff == 0)
            {
                return true;
            }
        }

        return false;
    }
};

//
class Solution3 {
public:
    bool checkInclusion(string s1, string s2) {
        int s1_len = s1.size();
        int s2_len = s2.size();
        if(s1_len > s2_len)
        {
            return false;
        }

        vector<int> cnt(26);
        for(int i = 0;i < s1_len;++i)
        {
            --cnt[s1[i] - 'a'];
        }

        int left = 0;
        //slide window,check if window size equal to s1 length
        for(int right = 0; right < s2_len;++right)
        {
            ++cnt[s2[right]-'a'];
            //s2[right]-'a' not in the s1 or not balanced
            //slide left to right
            while(cnt[s2[right]-'a'] > 0)
            {
                --cnt[s2[left]-'a'];
                ++left;
            }

            if(right - left + 1 == s1_len)
            {
                return true;
            }
        }
        return false;
    }
};